#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        //计算有多少行，每一行有多少个数据
        int m = matrix.size();
        int n = matrix[0].size();

        for(int i = 0; i < m; i++)
        {
            //判断该行的最大值是如果小于target，判断下一行
            if(matrix[i][n - 1] < target)
                continue;

            //二分查找
            int left = 0, right = n - 1;
            while(left <= right)
            {
                int mid = (right - left) / 2 + left;
                if(matrix[i][mid] > target)
                    right = mid - 1;
                else if(matrix[i][mid] < target)
                    left = mid + 1;
                else
                    return true;
            }
            return false;
        }
        return false;
    }
};